/**
 * 利用完全二叉树性质
 * @param {TreeNode} root
 * @return {number}
 */

const countNodes = root => {
  if (!root) return 0

  let left = root.left,
    right = root.right,
    leftHeight = 0,
    rightHeight = 0
  while (left) {
    left = left.left
    leftHeight += 1
  }
  while (right) {
    right = right.right
    rightHeight += 1
  }
  if (leftHeight === rightHeight) {
    return Math.pow(2, leftHeight + 1) - 1
  }
  return countNodes(root.left) + countNodes(root.right) + 1
}

const root = {
  val: 3,
  left: {
    val: 9,
    left: null,
    right: null
  },
  right: {
    val: 20,
    left: {
      val: 15,
      left: null,
      right: null
    },
    right: {
      val: 7,
      left: null,
      right: null
    }
  }
}

console.log(countNodes(root))